1. Field of the Invention
The present invention generally relates to dynamic, run-time optimization and specialization of binary executables. More particularly, the invention relates to the identification of pseudo-invariant instructions in frequently executing program paths for use in such optimization systems.
2. Background of the Invention
Improving run-time software application performance in microprocessor systems is an important means of improving processor throughput and execution speeds. While it is possible to optimize application executables at compile time, such optimizations cannot account for all the possible variables that may affect run-time performance. A priori run-time optimization is difficult to predict and implement because most executable programs operate in varying systems with varying shared libraries and operating on varying inputs. Thus, while these applications may be executed on high-performance computer systems and the executables may be optimized using a static optimizing compiler, true run-time optimization may still offer improved application performance.
Many run-time optimizers depend on identifying instructions that are pseudo-invariant. Some optimizers may refer to this identification process as value profiling. An instruction is invariant or constant if it produces the same output value every time it is executed. An instruction is pseudo-invariant if it is invariant or if it produces a limited set of output values almost every time it is executed. Instruction output is highly dependent on input data, so any given instruction may be pseudo-invariant at run-time, but not necessarily so at static compile time.
In addition, an instruction may be pseudo-invariant when reached along a particular path of program control, but not pseudo-invariant when reached along other paths. For example, consider a program comprising two function calls, each along a different path. If each call site passes a different constant argument, then instructions in the function are not dynamically invariant, but they may be invariant along each path.
The identification of pseudo-invariant program instructions is exceptionally helpful if one can determine whether that portion of the code that includes the pseudo-invariant instructions consumes a large quantity of system resources. Sequences of instructions are said to be expensive or “hot” if they take a long time to execute. If a portion of the code is expensive in this manner and it includes a pseudo-invariant instruction, the entire portion of the code may be optimized. The actual method of optimization is left to the optimizer or specializer in which this method is incorporated. Determination of the relative cost of a piece of code is important because it makes little sense to optimize a piece of code if it is inexpensive, even if the code includes pseudo-invariant instructions. The only time benefits are seen is when an expensive piece of code with pseudo-invariant instructions is located and optimized.
A number of methods have been proposed for finding and classifying pseudo-invariant instructions. One method involves the addition of instrumentation code to a program and running the modified program over a training set. This method produces accurate data value profiles for the application, but is not able to classify paths as hot. Further, since the instrumentation code cannot be removed, this method of value profiling adds considerable overhead.
Another method of value profiling invokes an interpreter at run-time via a sampling interrupt. The interpreter, which is a separate piece of code that interprets the instructions, evaluates a single block of the program and then switches control back to the original program to continue execution of the program. This method is fast, but does not generate path information. Therefore the information produced is limited.
Another proposed method uses an interpreter over the entire program to find path information. This method, however does not produce value information to determine if instructions are pseudo-invariant.
In general, the prior art is not capable of both locating expensive program paths and determining if those paths contain pseudo-invariant instructions. Furthermore, the prior art does not collect and store this information in a manner that is useful to an application optimizer or specializer.
It is desirable therefore, to develop a method of dynamically identifying pseudo-invariant instructions on frequently executed program paths. The method preferably incurs low overhead and prepares the data in a form that is easily adaptable to a variety of program optimizers and specializers.